1. Field of the Invention
This invention relates to a mechanism for creating dependency free code and more particularly to such a mechanism for employment with a plurality of concurrent processing elements.
2. Description of the Prior Art
Most computers today are still of the von Neumann type that are driven by or execute imperative languages which are sequential in nature. Furthermore, such sequential languages contain many dependencies between the instructions so that individual instructions cannot be executed out of order. For example, consider the sequences EQU C:=Fn(A,B) EQU D:=Fn+i(C,E).
The two functions Fn and Fn+i are said to be logically dependent since the result of function Fn is used as an input to the next function Fn+i.
A further disadvantage of sequential languages is that when sequences or loops are repeated, there is a redundancy in memory fetches and code processing which, if removed, would increase the throughput of the processor.
One manner in which the throughput of a processing system has been increased has been by employing a plurality of processors in a multiprocessing mode. However, the individual processors still must execute instructions in sequence and the only concurrency that exists is when the respective processors are executing different segments of a program or entirely different programs. Such multiprocessing systems are disclosed for example, in Mott et al., U.S. Pat. No. 3,319,226 and Anderson et al., U.S. Pat. No. 3,419,849.
Still another attempt at increasing throughput has been the employment of pipelining wherein the various subfunctions of an instruction execution are overlapped. That is to say, each instruction requires an instruction processing step, a reference processing step and an execution processing step. By overlapping these steps with successive instructions, an instruction execution can be done each clock time thereby increasing the processor's throughput.
All of these methods for increasing throughput are designed for sequential instruction execution because of the logical dependency between instructions as was indicated above. Because of the logical dependency, true concurrent processing cannot be achieved wherein the various instructions could be executed independently of each other so as to readily accommodate processing by a cluster or multiple of processing elements.
Applicative languages differ from imperative languages in that the respective statements are by nature independent of one another and thus can be implemented concurrently by a network of processing elements designed to reduce such applicative statements. An example of such applicative language processors is given in the Bolton et al. patent application U.S. Ser. No. 281,064 and the Hagenmaier et al. patent application, U.S. Ser. No. 281,065, both of which were filed July 7, 1981 and assigned to the assignee of the present application. Such applicative languages differ from imperative languages in that they are, by design, not sequential in the von Neumann sense. However, most of the program libraries that are employed today have been written in imperative languages and any update or future generations of data processing systems which are to employ those libraries must be adapted to execute imperative languages.
One manner in which throughout can be increased is to recognize segments of the object code which do not depend upon results of previous operations and to form these segments into independent sequences or queues which then can be processed concurrently by a plurality of processing elements. This of course, requires the management of operands in such a manner that an operation can be performed on an operand without destroying its original value as it exists in the memory. Different symbolic names can be assigned to reference a given data item for this purpose. In turn, the formation of such queues of code or symbols further accommodate concurrent processing by the processing units.
It is then an object of the present invention for providing an improved mechanism for creating dependency free instruction code.
It is another object of the present invention to provide dependency free instruction code for execution by multiple processing elements.
It is still another object of the present invention to provide an improved mechanism to supply dependency free instruction code to a plurality of processing elements in a concurrent manner.
It is still further object of the present invention to provide a mechanism for creating an instruction code that is free of redundant memory fetches and which code is of such nature that it does not have to be reprocessed for the processing of sequences of such code.